package secondary

/*
	给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
	一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

	示例 1:

	输入: 12258
	输出: 5
	解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
	提示：

	0 <= num < 231

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func TranslateNum(num int) int {
	return translateNum(num)
}

/*
	将数字翻译成字符串、按照以上规则如果只考虑1位、则有一种方式、如果考虑两位、则需要看前1位的大小
	给定f(i)表示[0...i]的组合
	1. 只考虑当前位: f(n)=f(n-1)
	2. 考虑前一位:
		2.1 nums[i-1]=1: f(n) = f(n-1)+f(n-2)
		2.2 nums[i-1]=2: nums[i]>=0&&nums[i]<=5, f(n) = f(n-1)+f(n-2)、否则f(n)=f(n-1)

*/
func translateNum(num int) int {
	if num == 0 {
		return 1
	}
	nums := make([]int, 0)
	for num > 0 {
		nums = append([]int{num % 10}, nums...)
		num /= 10
	}
	dp := make([]int, len(nums))
	dp[0] = 1
	for i := 1; i < len(nums); i++ {
		dp[i] = dp[i-1]
		if  nums[i-1] == 1 {
			if i >= 2 {
				dp[i] += dp[i-2]
			} else {
				dp[i] += 1
			}

			continue
		}
		if  nums[i-1] == 2 && nums[i] >= 0 && nums[i] <= 5 {
			if i >= 2 {
				dp[i] += dp[i-2]
			} else {
				dp[i] += 1
			}
			continue
		}
	}
	return dp[len(dp)-1]
}
